package demo.practice.binary_search;

public class P441 {
    /* 1+2+3+i<n
    ¤
    ¤ ¤
    ¤ ¤ ¤
    ¤ ¤

    (i+1)i/2 <=n
    i*i+i<=2n
    i(i+1)/2 <=n
            */

    public static void main(String[] args) {
        P441 p441= new P441();
        p441.arrangeCoins(1804289383);

    }
    public int arrangeCoins(int n) {
        int min = 1;
        int max =  n;

        while (max >= min) {
            int mid = min + (max - min) / 2;



            if ((mid>>1)  * (mid + 1) <=  n  && ((mid + 1)>>1) *(mid + 1 + 1) >   n)
                return mid;

            if ((mid>>1)  * (mid + 1) >  n)//mid偏大
                max = mid - 1;

            if (((mid + 1)>>1)  * (mid + 1 + 1) <  n) //mid偏小
                min = mid + 1;
        }

        return 0;
    }

}
